package com.learn.algorithm.tree;

import java.util.Arrays;

// https://www.nowcoder.com/practice/c552d3b4dfda49ccb883a6371d9a6932
public class NowCoderCountConsistentKeys {
    public static int[] countConsistentKeys(int[][] b, int[][] a) {
        build();
        StringBuilder builder = new StringBuilder();
        for (int[] s : a) {
            for (int i = 1; i < s.length; i++) {
                builder.append(s[i] - s[i - 1]).append("#");
            }
            insert(builder.toString());
            builder.setLength(0);
        }
        int[] ans = new int[b.length];
        for (int i = 0; i < b.length; i++) {
            int[] nums = b[i];
            for (int j = 1; j < nums.length; j++) {
                builder.append(nums[j] - nums[j - 1]).append("#");
            }
            ans[i] = count(builder.toString());
            builder.setLength(0);
        }
        clear();
        return ans;
    }

    public static void clear() {
        for (int i = 1; i < cnt; i++) {
            Arrays.fill(tree[i], 0);
            pass[i] = 0;
        }
    }

    public static final int MAX = 15001;
    public static int[][] tree = new int[MAX][12];
    public static int[] pass = new int[MAX];
    public static int cnt;

    public static void build() {
        cnt = 1;
    }

    public static int path(char c) {
        if (c == '#') {
            return 10;
        } else if (c == '-') {
            return 11;
        } else {
            return c - '0';
        }
    }

    public static void insert(String word) {
        int current = 1;
        pass[current]++;
        for (int i = 0; i < word.length(); i++) {
            int path = path(word.charAt(i));
            if (tree[current][path] == 0) {
                tree[current][path] = ++cnt;
            }
            current = tree[current][path];
            pass[current]++;
        }
    }

    public static int count(String word) {
        int current = 1;
        for (int i = 0; i < word.length(); i++) {
            int path = path(word.charAt(i));
            if (tree[current][path] == 0) {
                return 0;
            }
            current = tree[current][path];
        }
        return pass[current];
    }
}
